#define _CRT_SECURE_NO_WARNINGS 1


#include "Heap.h"

//int main()
//{
//	//如何把以下数组变成一个堆
//	//int a[] = { 50, 100, 70, 65, 60, 32 };
//	int a[] = { 60, 70, 65, 50, 32, 100 };
//
//	HP hp;
//	HPInit(&hp);
//
//	for (int i = 0; i < sizeof(a) / sizeof(int); i++)
//	{
//		HPPush(&hp, a[i]);
//	}
//
//	//printf("%d\n", HPTop(&hp));
//	//HPPop(&hp);
//	//printf("%d\n", HPTop(&hp));
//	
//	while (!HPEmpty(&hp))
//	{
//		printf("%d\n", HPTop(&hp));
//		HPPop(&hp);
//	}
//
//	HPDestroy(&hp);
//	
//	return 0;
//}


//int main()
//{
//	//如何把以下数组变成一个堆
//	//int a[] = { 50, 100, 70, 65, 60, 32 };
//	int a[] = { 60, 70, 65, 50, 32, 100 };
//
//	HP hp;
//	HPInitArray(&hp, a, sizeof(a) / sizeof(int));
//
//	while (!HPEmpty(&hp))
//	{
//		printf("%d\n", HPTop(&hp));
//		HPPop(&hp);
//	}
//
//	HPDestroy(&hp);
//
//	return 0;
//}


//void HeapSort(int* a, int n)
//{
//	HP hp;
//	HPInitArray(&hp, a, n);
//	int i = 0;
//
//	while (!HPEmpty(&hp))
//	{
//		a[i++] = HPTop(&hp);
//		HPPop(&hp);
//	}
//
//	HPDestroy(&hp);
//}


////升序，建大堆还是小堆呢？大堆
////O(N * logN)
//void HeapSort(int* a, int n)
//{
//	//a数组直接建堆 O(N)
//	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
//	{
//		AdjustDown(a, n, i);
//	}
//
//	//O(N * logN)
//	int end = n - 1;
//
//	while (end > 0)
//	{
//		Swap(&a[0], &a[end]);
//		AdjustDown(a, end, 0);
//		--end;
//	}
//}
//
//int main()
//{
//	int a[] = { 3, 6, 1, 5, 8, 9, 2, 7, 4, 0 };
//
//	HeapSort(a, sizeof(a) / sizeof(int));
//
//	return 0;
//}


void CreateNDate()
{
	//造数据
	int n = 100000;
	srand((unsigned int)time(0));
	const char* file = "data.txt";
	FILE* fin = fopen(file, "w");

	if (NULL == fin)
	{
		perror("fopen error");
		return;
	}

	for (int i = 0; i < n; ++i)
	{
		//随机数系统规定只有三万多个
		//+i 是为了让数据的随机性更大一点
		//%1000000 是为了让数据在1000000以内，这样我们可以手动让几个数据大于1000000，以此来验证我们程序的正确性
		int x = (rand() + i) % 1000000;
		fprintf(fin, "%d\n", x);
	}

	fclose(fin);
}

void topk()
{
	printf("请输入k:>");
	int k = 0;
	scanf("%d", &k);

	const char* file = "data.txt";
	FILE* fout = fopen(file, "r");

	if (NULL == fout)
	{
		perror("fopen error");
		return;
	}

	int* minheap = (int*)malloc(sizeof(int) * k);

	if (NULL == minheap)
	{
		perror("malloc error");
		return;
	}

	for (int i = 0; i < k; i++)
	{
		fscanf(fout, "%d", &minheap[i]);
	}

	//建k个数据的小堆
	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(minheap, k, i);
	}

	int x = 0;

	while (fscanf(fout, "%d", &x) != EOF)
	{
		//读取剩余数据，比堆顶的值大，就替换它进堆
		if (x > minheap[0])
		{
			minheap[0] = x;
			AdjustDown(minheap, k, 0);
		}
	}

	for (int i = 0; i < k; i++)
	{
		printf("%d ", minheap[i]);
	}

	fclose(fout);
	free(minheap);
	minheap = NULL;
}

int main()
{
	CreateNDate();
	topk();

	return 0;
}